package com.example.leetcode;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.stream.Collectors;

public class Leedcode {

    public static void main(String[] args) {
        int[][] nums1 = {{1, 2}, {3, 4}};
        int[] nums2 = {4, 4, 8, 9, 9};

        Leedcode leedcode = new Leedcode();
//        int[] intersect = leedcode.intersect01(nums1, nums2);
//        System.out.println(Arrays.toString(intersect));

        //   System.out.println(leedcode.maxProfit(nums1));
        //       System.out.println(  Arrays.toString(leedcode.matrixReshape(nums1,1,4)));
//        List<List<Integer>> generate = leedcode.generate(5);
//
//        generate.forEach(p -> {
//            p.forEach(System.out::print);
//            System.out.println();
//        });

        char[][] chars =

            {{'.', '.', '.', '.', '5', '.', '.', '1', '.'}
                , {'.', '4', '.', '3', '.', '.', '.', '.', '.'}
                , {'.', '.', '.', '.', '.', '3', '.', '.', '1'},
                {'8', '.', '.', '.', '.', '.', '.', '2', '.'}
                , {'.', '.', '2', '.', '7', '.', '.', '.', '.'}
                , {'.', '1', '5', '.', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '2', '.', '.', '.'}
                , {'.', '2', '.', '9', '.', '.', '.', '.', '.'}
                , {'.', '.', '4', '.', '.', '.', '.', '.', '.'}};

    //    System.out.println(leedcode.isValidSudoku(chars));
    }

    /*


        public int[] intersect(int[] nums1, int[] nums2) {
            Arrays.sort(nums1);
            Arrays.sort(nums2);
            List<Integer> integerList = new ArrayList<>();
            int k1 = 0, k2 = 0;
            while ((k1 < nums1.length) && (k2 < nums2.length)) {

                if (nums1[k1] == nums2[k2]) {
                    integerList.add(nums1[k1]);
                    k2++;
                    k1++;
                    continue;
                }
                if (nums1[k1] < nums2[k2]) {
                    k1++;
                    continue;
                }
                if (nums1[k1] > nums2[k2]) {
                    k2++;
                    continue;
                }


            }

            int[] res = new int[integerList.size()];
            for (int i = 0; i < integerList.size(); i++) {
                res[i] = integerList.get(i);
            }
            return res;

        }

        public int[] intersect01(int[] nums1, int[] nums2) {
            Set<Integer> integerList = new HashSet<>();

            Set<Integer> set = new HashSet<>();
            for (int nums : nums1
            ) {
                set.add(nums);
            }
            for (int nums : nums2) {
                if (!set.add(nums)) {
                    integerList.add(nums);
                }
            }

            int[] res = new int[integerList.size()];

            Iterator it = integerList.iterator();
            int i = 0;
            while (it.hasNext()) {
                res[i] = (int) it.next();
                i++;
            }

            return res;
        }

        public int[] intersacti02(int[] nums1, int[] nums2) {
            //数组转换成List
            List<Integer> list1 = Arrays.stream(nums1)
                .boxed()
                .collect(Collectors.toList());
    //
    //        int[] nums1=new int[];
    //        List<Integer> collect = Arrays.stream(nums1).boxed().collect(Collectors.toList());
    //

            List<Integer> list2 = Arrays.stream(nums2)
                .boxed()
                .filter(num -> {
                    if (list1.contains(num)) {
                        list1.remove(num);
                        return true;
                    }
                    return false;
                })
                .collect(Collectors.toList());  //stream->list

            int[] res = new int[list2.size()];
            for (int i = 0; i < list2.size(); i++) {
                res[i] = list2.get(i);
            }
            return res;
        }


        public int maxProfit(int[] prices) {

            int res = 0;
            int res1 = 0;
            TreeMap<Integer, Integer> map = new TreeMap<>();
            //TreeSet<Integer> collect = Arrays.stream(prices).boxed().collect(Collectors.toCollection(TreeSet::new));
            for (int price : prices) {
                if (map.containsKey(price)) {
                    map.put(price, map.get(price) + 1);
                }
                map.putIfAbsent(price, 0);
            }

            if (map.size() <= 1) {
                return 0;
            }
            for (int i = 0; i < prices.length - 1; i++) {
                if (map.get(prices[i]) > 0) {
                    map.put(prices[i], map.get(prices[i]) - 1);
                } else {
                    map.remove(prices[i]);
                }
                Integer last = map.lastKey();
                res1 = last - prices[i];
                if (res < res1) {
                    res = res1;
                }
            }
            return res;
        }

        public int[][] matrixReshape(int[][] mat, int r, int c) {
            int wide = mat[0].length;
            int height = mat.length;
            if (wide * height != r * c) {
                return mat;
            }
            int[][] newMat = new int[r][c];
            int r1 = 0, c1 = 0;
            for (int[] matH : mat) {
                for (int matW : matH) {
                    if (c1 < c) {
                        newMat[r1][c1] = matW;
                        c1++;
                    }
                    if (c1 == c) {
                        c1 = 0;
                        r1++;
                    }


                }
            }
            return newMat;

        }

        public List<List<Integer>> generate(int numRows) {
            List<List<Integer>> lists = new ArrayList<>(numRows);
            ArrayList<Integer> integers = new ArrayList<>();
            integers.add(1);
            lists.add(integers);
            if (numRows == 1) {
                return lists;
            }
            for (int i = 1; i < numRows; i++) {
                ArrayList<Integer> temple1 = new ArrayList<>();
                temple1.add(1);
                List<Integer> integerList = lists.get(i - 1);
                for (int j = 1; j < i; j++) {
                    temple1.add(integerList.get(j) + integerList.get(j - 1));
                }
                temple1.add(1);
                lists.add(temple1);
            }
            return lists;


        }

    *//*

    public boolean isValidSudoku(char[][] board) {

        for (int i = 0; i < 9; i++) {
            Set<Character> set = new HashSet<>();
            Set<Character> set1 = new HashSet<>();
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    if (!set.add(board[i][j])) {
                        return false;
                    }
                }
                if (board[j][i] != '.') {
                    if (!set1.add(board[j][i])) {
                        return false;
                    }
                }
            }
        }

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                Set<Character> set = new HashSet<>();
                for (int i1 = 0; i1 < 3; i1++) {
                    for (int j1 = 0; j1 < 3; j1++) {
                        char c = board[i1 + 3 * i][j1 + 3 * j];
                        if ( c!= '.') {
                            if (!set.add(c)) {
                                return false;
                            }
                        }


                    }


                }


            }


        }

        return true;
    }

*/

        public void setZeroes(int[][] matrix) {
            TreeSet<Integer> line = new TreeSet<>();
            TreeSet<Integer> vertical = new TreeSet<>();
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    int matrix1 = matrix[i][j];
                    if (matrix1 == 0) {
                        line.add(j);
                        vertical.add(i);
                    }
                }
            }
            for (int i = 0; i < matrix.length; i++) {
                if (vertical.contains(i)) {
                    for (int j = 0; j < matrix[0].length; j++) {
                        matrix[i][j] = 0;
                    }
                    continue;
                }
                for (int j = 0; j < matrix[0].length; j++) {
                    if (line.contains(j)) {
                        matrix[i][j] = 0;
                    }
                }
            }
        }


}
